/*
 *  Copyright 2007-2008 by Matthias Buch-Kromann <mbk.isv@cbs.dk>.
 *
 *  This file is part of the Open-source Dependency Toolkit (OSDT),
 *  see http://code.google.com/p/open-source-dependency-toolkit.
 *  
 *  The OSDT is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as 
 *  published by the Free Software Foundation, either version 3 of 
 *  the License, or (at your option) any later version.
 * 
 *  The OSDT is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 * 
 *  You should have received a copy of the GNU Lesser General Public 
 *  License along with the OSDT in the files COPYING and COPYING.LESSER.
 *  If not, see http://www.gnu.org/licenses.
 */

package org.osdtsystem.graphs.views;

import java.util.List;
import org.osdtsystem.exceptions.IllegalCycleException;
import org.osdtsystem.exceptions.NodeNotFoundException;
import org.osdtsystem.values.EdgeID;
import org.osdtsystem.values.NodeID;

/**
 * Public interface for an unordered directed tree with edge relation labels. 
 * @author Matthias Buch-Kromann <mbk.isv@cbs.dk>
 */
public interface ProjectiveTree extends Tree {
    
   // Construction methods
    /**
     * Add a new child node at the given position and parent with the given edge 
     * relation. Functionally equivalent to moveSubtree(node, parent, position, relation)
     * where <code>node</code> is the newly created node.
     * @param parent the parent node
     * @param position the position of the new node at the parent
     * @param relation the edge relation
     * @return the new node
     * @throws NodeNotFoundException if the parent node is not in the tree
     */
    public NodeID addNode(NodeID parent, int position, Object relation)
            throws NodeNotFoundException;

    /**
     * Move a subtree by specifying the root of the subtree (the subroot), its 
     * new parent, the new relation, and the position at which the node is 
     * inserted relative to the node's siblings
     * at the new parent. See the description of the position() method.
     * Invalid positions are always replaced with their nearest valid position (eg,
     * if there are three left siblings, the position -1000 is equivalent to -4). 
     * The operation is not performed if it results in a cycle (ie, a non-tree);
     * in this case, the tree is left unchanged and an exception is thrown. 
     * @param subroot the root node of the subtree
     * @param parent the new parent node
     * @param position the new position of the node at the parent
     * @param relation the edge relation
     * @return the new edge
     * @throws NodeNotFoundException if one of the nodes is non-existent
     * @throws IllegalCycleException if the operation would result in a cyclic graph
     */
    public EdgeID moveSubtree(NodeID subroot, NodeID parent, int position, Object relation)
            throws NodeNotFoundException, IllegalCycleException;

    
    // Query methods
    
    // Local: Moving from parent to children
    /**
     * The outer left child of the given node.
     * @param parent the node
     * @return the outer left child; <code>null</code>
     * if no such node exists
     */        
    public NodeID outerLeftChild(NodeID parent);

    /**
     * The inner left child of the given node.
     * @param parent the node
     * @return the inner left child; <code>null</code>
     * if no such node exists
     */        
    public NodeID innerLeftChild(NodeID parent);
    
    /**
     * The inner right child of the given node.
     * @param parent the node
     * @return the inner right child; <code>null</code>
     * if no such node exists
     */            
    public NodeID innerRightChild(NodeID parent);
    
    /**
     * The outer right child of the given node.
     * @param parent the node
     * @return the outer right child; <code>null</code>
     * if no such node exists
     */         
    public NodeID outerRightChild(NodeID parent);

    /**
     * Is the child to the left of its parent?
     * @param child the child node
     * @return <code>true</code> if the child precedes its parent, <code>false</code>
     * otherwise.
     */
    public boolean inLeftField(NodeID child);

    /**
     * Is the child to the right of its parent?
     * @param child the child node
     * @return <code>true</code> if the child comes after its parent, <code>false</code>
     * otherwise.
     */
    public boolean inRightField(NodeID child);
    
    /**
     * Return the number of children in the left field of the parent.
     * @param parent the parent
     * @return the number of left children
     */
    public int leftChildren(NodeID parent);
    
    /**
     * Return the number of children in the right field of the parent.
     * @param parent the parent
     * @return the number of right children
     */
    public int rightChildren(NodeID parent);

    
    // Local: Moving between siblings
    /**
     * The sibling to the immediate left of the node (but on the same side of
     * the parent). 
     * @param node the node
     * @return the sibling to the immediate left; <code>null</code>
     * if no such node exists
     */    
    public NodeID leftSibling(NodeID node);

    /**
     * The sibling to the immediate right of the node (but on the same side of
     * the parent). 
     * @param node the node
     * @return the sibling to the immediate right; <code>null</code>
     * if no such node exists
     */    
    public NodeID rightSibling(NodeID node);

    /**
     * The inner sibling of the given node.
     * @param node the node
     * @return the inner sibling of the node; <code>null</code> if it doesn't exist.
     */
    public NodeID innerSibling(NodeID node);

    /**
     * The outer sibling of the given node.
     * @param node the node
     * @return the outer sibling of the node; <code>null</code> if it doesn't exist.
     */
    public NodeID outerSibling(NodeID node);
    
   
    // Non-local: Computing the roof edge for a node
    /**
     * The roof edge for the given node, ie, the shortest edge in the tree that
     * contains the node within its span. Because the tree is projective, the roof
     * edge can be found as the edge connecting the node or its lowest tr: if the node is after its parent, the roof edge
     * is the first forward-goin
     * 
     * can be identified as the first transitive sibling edge that points in 
     * the same direction as the original edge 
     * 
     * follows: The roof edge is 
     * A transitive sibling is a sibling of theif the 
     * node comes after its parent, the roof edge will be the 
     * 
     * 
     * 's edge to its parent points  points back/forwards, the roof will be the first sibling edge at a 
     * transitive parent that comes 
     * edge on the same side of the parent that  points in the other dire the other way
     * @param node the node
     * @return the roof edge
     */
    public EdgeID roof(NodeID node);
    

    // Non-local: Moving between adjacent nodes
    /**
     * The node to the immediate left of the given node in the linear node order
     * defined by the projective tree.
     * @param node the node
     * @return the node to the immediate left of the given node; <code>null</code>
     * if no such node exists
     */
    public NodeID left(NodeID node);
    
    /**
     * The node to the immediate right of the given node in the linear node order
     * defined by the projective tree. 
     * @param node the node
     * @return the node to the immediate right of the given node; <code>null</code>
     * if no such node exists
     */
    public NodeID right(NodeID node);

    
    // Non-local: Moving from root to boundary nodes
    /**
     * The left boundary of the given node, defined as the left-most node
     * in the yield of the node.
     * @param node the node
     * @return the left-most node in the yield of the node
     */
    public NodeID leftBoundary(NodeID node);
    
    /**
     * The right boundary of the given node, defined as the right-most node
     * in the yield of the node.
     * @param node the node
     * @return the right-most node in the yield of the node
     */
    public NodeID rightBoundary(NodeID node);
   
    /**
     * The highest transitive parent (or the node itself) that has the node on 
     * its left periphery.
     * @param node the node
     * @return the highest node in the tree that non-strictly dominates the node
     * and has the node in its left periphery.
     */
    public NodeID highestLeftPeripheryParent(NodeID node);

    /**
     * The highest transitive parent (or the node itself) that has the node on 
     * its right periphery.
     * @param node the node
     * @return the highest node in the tree that non-strictly dominates the node
     * and has the node in its right periphery.
     */
    public NodeID highestRightPeripheryParent(NodeID node);

    /**
     * The highest transitive parent (or the node itself) that has the node on 
     * its left or right periphery.
     * @param node the node
     * @return the highest node in the tree that non-strictly dominates the node
     * and has the node in its left or right periphery.
     */
    public NodeID highestPeripheryParent(NodeID node);

    /**
     * The list of all nodes on the left periphery of the given node.
     * @param node the node
     * @return the left periphery
     */
    public List<NodeID> leftPeriphery(NodeID node);

    /**
     * The list of all nodes on the right periphery of the given node.
     * @param node the node
     * @return the right periphery
     */
    public List<NodeID> rightPeriphery(NodeID node);
            
    // Finding potential parent attachment sites
    /**
     * Is the given site an adjacent parent site for the given node, ie, can we 
     * attach the node to the potential parent site without affecting 
     * the projectivity or the underlying node order? Or equivalently, if 
     * Y(n) denotes the yield of node n, is it the case that no other node is 
     * located between Y(site)-Y(node) and Y(node), and that Y(node) is not 
     * located between any two nodes in Y(site)-Y(node)?
     * @param node the node
     * @param site the potential parent site
     * @return the position where the node would be inserted projectively
     * to the parent site, or 0 if the attachment would change the ordering
     */
    public int projectiveParentSite(NodeID node, NodeID site);
    
    /**
     * The list of all adjacent parent sites for the given node.
     * @param node the node
     * @return the list of adjacent parent sites
     */
    public List<LandingSite> projectiveParentSites(NodeID node);
    
    public NodeID lowestLeftTransitiveParent(NodeID node);
    
    /**
     * The position of the node relative to its siblings. Negative positions are 
     * to the left of the parent, positive positions to the right of the parent, 
     * as follows (position 0 is undefined):
     * <blockquote>
     * ... [-3] sibling [-2] sibling [-1] PARENT [1] sibling [2] sibling [3] ...
     * </blockquote>
     * @param node the node
     * @return the position of the node; 0 if the node does not have a parent
     */

    public int position(final NodeID node);
   
    /**
     * The list of all subnodes at the given node, in the order defined by the tree.
     * @param node the node
     * @return the ordered list of nodes in the subtree rooted by the node
     */
    public List<NodeID> subnodesInOrder(NodeID node);
    
    
    /**
     * Inner class representing a landing site consisting of a parent node and 
     * a position at the parent. 
     */
    public class LandingSite implements Comparable {
        final public NodeID parent;
        final public int position;
        LandingSite(NodeID parent, int position) {
            this.parent = parent;
            this.position = position;
        }
        @Override
        public String toString() {
            return parent + ":" + position;
        }
        @Override
        public int compareTo(Object siteUnchecked) {
            LandingSite site = (LandingSite) siteUnchecked;
            int result = parent.compareTo(site.parent);
            return (result == 0) ? position - site.position : result;
        }
    }
}
